import java.util.PriorityQueue;
import java.util.Stack;



public class FordFulkeson {
	protected int f[][];
	protected int c[][];
//	protected int g[][];
	protected int n;
	protected int max_flow=0;
	protected int minPath= 100000;
	protected Stack<Integer> arrange;
	
	public FordFulkeson () {		
	}
		
	public int minPath1(int[] shortestPath,int[][]c,int[][]h,int[][]f,int numberofvertes) {
		System.out.println("Matrix capacity");
		n=numberofvertes;
		for (int i = 0; i <n ; i++) {
			for (int j = 0; j < n; j++) {
					System.out.print(c[i][j]);
					System.out.print("\t");
							
			}	
			System.out.print("\n");
		}
		int t,v;
		//caculate minPath 
		t=shortestPath[shortestPath.length-1];
		for(int i=shortestPath.length-2;i>=0;i--){
			v=shortestPath[i];
//			System.out.println(t);
//			System.out.println(v);			
			minPath=min(minPath,c[t-1][v-1]);
			t=v;
		}
		
		System.out.println("minpath"+minPath);
		//matrix increment flow
		int i=shortestPath.length-1;
		for(int j=shortestPath.length-2;j>=0;j--)
		{
			System.out.println(shortestPath[i]+","+shortestPath[j]);
			f[shortestPath[i]][shortestPath[j]]+=minPath;
			f[shortestPath[j]][shortestPath[i]]-=minPath;
			i=j;
		}
		System.out.println("matrix f");
		for(int x=0;x<n;x++)
		{
			for(int y=0;y<n;y++)
			{
				System.out.print(f[x][y]);
				System.out.print("\t");
			}
			System.out.print("\n");
		}
		//max_flow+=minPath;
		//matrix resudial network
		int j=shortestPath.length-1;
		for(int k =shortestPath.length-2;k>=0;k--){
			if(c[shortestPath[j]][shortestPath[k]]!=10000){
				c[shortestPath[j]][shortestPath[k]]=c[shortestPath[j]][shortestPath[k]]-f[shortestPath[j]][shortestPath[k]];
				c[shortestPath[k]][shortestPath[j]]=c[shortestPath[k]][shortestPath[j]]-f[shortestPath[k]][shortestPath[j]];
				j=k;
			}
			if(c[shortestPath[j]][shortestPath[k]]==0)
			{
				c[shortestPath[j]][shortestPath[k]]=1000;
			}
			}
		System.out.println("matrix G");
		for(int x=0;x<n;x++)
		{
			for(int y=0;y<n;y++)
			{
				System.out.print(c[x][y]);
				System.out.print("\t");
			}
			System.out.print("\n");
		}
		
		return minPath;
	}
	
	public int [][] getMatrixCapacity()
	{
		
		return c;
	}
	public static int min(int a, int b)
	{
		if(a>b)
			return b;
		else
			return a;
	}
}
